package yellow.pe.javaVersion;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * https://pe-cn.github.io/3/
 *
 * Problem 3
 * Largest prime factor
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * What is the largest prime factor of the number 600851475143?
 *
 */
public class PE0003_2 {

    public static void main(String[] args) {

        //Long b = 13195L;
        Long b = 600851475143L;
        ArrayList<Long> ab = getPrimeFactors(b);
        Long[] bi = ab.toArray(Long[]::new);
        System.out.println(Arrays.toString(bi));
        ab.sort(Comparator.naturalOrder());
        System.out.println(bi[bi.length-1]);
    }

    public static ArrayList<Long> getPrimeFactors(Long n) {
        ArrayList<Long> ab = new ArrayList<Long>();
        Long i = 2L;
        while (i*i<=n) {
            if (isPrimeNumber(i) && (n%i == 0)) {
                ab.add(i);
                if (isPrimeNumber(n/i)) ab.add(n/i);
            }
            i++;
        }
        return ab;
    }

    public static Boolean isPrimeNumber(Long n) {
        Long i = 2L;
        if (n%i==0) return false;
        for(i=3L;i*i<=n;i+=2L)
            if (n%i==0) return false;
        return true;
    }
}
